//package dateStructure;
//
//import java.util.Scanner;
//
//public class seniorDatestructure {
//    //并查集算法
//    public static void main(String args[]){
//        Scanner scanner=new Scanner(System.in);
//        System.out.println("请依次输入总人数与关系数：");
//        int n=scanner.nextInt();
//        int m=scanner.nextInt();
//        int father[]=new int[n+1];
//        init(father,n);
//        System.out.println("请输入有关系的两个人的索引号：");
//        while (m-->0){
//            int u=scanner.nextInt();
//            int v=scanner.nextInt();
//            merge(father,u,v);
//        }
//        System.out.println("每个人的祖宗为：");
//        for(int i=1;i<=n;i++){
//            System.out.print(father[i]+"\t");
//        }
//        System.out.println();
//        int sum=0;
//        for(int i=1;i<=n;i++){
//           if(father[i]==i){
//               sum++;
//           }
//        }
//        System.out.println("家族数一共有："+sum);
//        System.out.println("请输入要判断关系的两个人的集合号：");
//        while (scanner.hasNext()){
//            int u=scanner.nextInt();
//            int v=scanner.nextInt();
//            System.out.println(findNum(father,u)==findNum(father,v)?"两人有血缘关系！":"两人没有关系！");
//        }
//    }
//
//    /**
//     *
//     * @param father 存储每个人当前祖宗集合号的数组
//     * @param u 人的集合号
//     * @param v 人的集合号
//     */
//    private static void merge(int father[],int u,int v){
//        //找到当前两个人的集合号
//        int p=findNum(father,u);
//        int q=findNum(father,v);
//        if(p==q){
//            return ;//如果两个人的集合号相同，及有相同的祖宗，说明有关系,不用操作
//        }
//        else if(p<q){//把小的集合号赋值到大的集合号上
//            father[q]=p;
//        }
//        else{//p>q
//            father[p]=q;
//        }
//    }
//    /**
//     *
//     * @param father 存储每个人当前祖宗集合号的数组
//     * @param x 每个人的下标索引
//     * @return 每个人的祖宗集合号
//     */
//    private static int findNum(int father[],int x){
//        if(x!=father[x]){//如果当前人的集合号和其本身的索引不相同的话，则开始向上找其祖宗
//            father[x]=findNum(father,father[x]);//一直向上递归
//        }
//        return father[x];//当前该人的集合号和其索引相同的时候，说明当前该人即为祖宗，找到了，开始返回，并开始将其后面的后代更新为
//    }
//    public static void init(int father[],int n){
//        for(int i=1;i<=n;i++){
//            father[i]=i;
//        }
//    }
//}
